//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
//
//
//
// 示例 1：
//
//
//输入：n = 2
//输出：2
//解释：有两种方法可以爬到楼顶。
//1. 1 阶 + 1 阶
//2. 2 阶
//
// 示例 2：
//
//
//输入：n = 3
//输出：3
//解释：有三种方法可以爬到楼顶。
//1. 1 阶 + 1 阶 + 1 阶
//2. 1 阶 + 2 阶
//3. 2 阶 + 1 阶
//
//
//
//
// 提示：
//
//
// 1 <= n <= 45
//
//
// Related Topics 记忆化搜索 数学 动态规划 👍 3037 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function climbStairs(n: number): number {

    //? 有dp[i]种方式
    //? 递推：前一步为dp[i - 1] 和前一步为dp[i - 2]的情况 故dp[i] =
    const dp : number[] = []
    dp[1] = 1
    dp[2] = 2
    for (let i = 3; i <= n; i ++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
};
//leetcode submit region end(Prohibit modification and deletion)
